package features.advance.leetcode.array.medium;

import features.advance.nowcoder.meituan.BubbleSort;

import java.util.Arrays;

/**
 *  剑指 Offer 45. 把数组排成最小的数
 *
 *  难度：中等
 *
 * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [10,2]
 * 输出: "102"
 * 示例 2:
 *
 * 输入: [3,30,34,5,9]
 * 输出: "3033459"
 *
 *
 * 提示:
 *
 * 0 < nums.length <= 100
 * 说明:
 *
 * 输出结果可能非常大，所以你需要返回一个字符串而不是整数
 * 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
 *
 * @author LIN
 * @date 2021-06-02
 */
public class Offer45 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int[] nums = {3,30,34,5,9};
        String s = solution.minNumber(nums);
        System.out.println(s);

        new BubbleSort().sort(nums,"heap");
        System.out.println(Arrays.toString(nums));


    }

    static class Solution{
        /**
         * 计算出所有情况，从中找出最小的那个数字（时间复杂度可能会很高）
         * 按照x+y < y+x的规则，进行排序
         * [3,6,15,30,34,5,9]
         *
         * @param nums
         * @return
         */
        public String minNumber(int[] nums){
            String[] tmp = new String[nums.length];

            for(int i=0;i<tmp.length;i++){
                tmp[i] = nums[i]+"";
            }
            quickSort(tmp,0,nums.length-1);
            StringBuilder sb = new StringBuilder();
            for (String num : tmp) {
                sb.append(num);
            }
            return sb.toString();
        }

        private void quickSort(String[] tmp, int p, int r) {
            if(p > r){
                return;
            }
            int i = p-1;
            String x =  tmp[r];
            for (int j = p; j <= r; j++) {
                if((tmp[j] +x).compareTo(x+tmp[j]) <= 0){
                    i++;
                    String t = tmp[i];
                    tmp[i] = tmp[j];
                    tmp[j] = t;
                }
            }
            quickSort(tmp,p,i-1);
            quickSort(tmp,i+1,r);
        }

    }

}
